//
// Created by postgres on 5/22/17.
//
#include "../include/08search/B-tree.h"

#define N 20 /*  数据元素个数 */
#define MiddleKey (m+1)/2;
#define MinKeyNum (m+1)/2-1;
#define MaxKeyNum m-1;
/*-----------------------------------------Search--------------------------------------------*/
//寻找在本节点中应该插入的位置
int Search(BTree T, KeyType k) {
    int i = 1, n = T->keynum;
    while (i <= n && T->data[i] <= k)
        i++;
    return i - 1;
}
//循环查找直到子树为空,如果找到就返回待插入节点、插入位置,找到标记flag为1
Result BTreeSearch(BTree T, KeyType k) {
    BTree p = T, q;
    int i = 0, found = 0;
    Result r;
    while (p && !found) {
        i = Search(p, k);
        if (i > 0 && p->data[i] == k)
            found = 1;
        else {
            q = p;
            p = p->child[i];
        }
    }
    if (found) {
        r.node = p;
        r.flag = 1;
        r.pos = i;
    } else {
        r.node = q;
        r.flag = 0;
        r.pos = i;
    }
    return r;
}

/*-----------------------------------------Delete--------------------------------------------*/
/*
 * B-树是二叉排序树的推广，中序遍历B-树同样可得到关键字的有序序列（具体遍历算法【参见练习】）。
    任一关键字K的中序前趋(后继)必是K的左子树(右子树)中最右(左)下的结点中最后(最前)一个关键字。
Step 1.
    若被删关键字K所在的结点非树叶，则用K的中序前趋(或后继)K'取代K，然后从叶子中删去K'。
Step 2.
     从叶子*x开始删去某关键字K的三种情形为：
  *情形一：
     若x->keynum>Min，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。
   注意：
   *情形二：若x->keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。
         若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，
         而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变；*y被移出一个关键字，故其keynum减1，
         因它原大于Min，故减少1个关键字后keynum仍大于等于Min；而*x中已移入一个关键字，故删K后*x中仍有Min个关键字。
         涉及移动关键字的三个结点均满足B-树的性质(3)。 请读者验证，上述操作后仍满足B-树的性质(1)。移动完成后，删除过程亦结束。
   *情形三：若*x及其相邻的左右兄弟(也可能只有一个兄弟)中的关键字数目均为最小值Min，
        则上述的移动操作就不奏效，此时须*x和左或右兄弟合并。不妨设*x有右邻兄弟*y(对左邻兄弟的讨论与此类似)，
        在*x中删去K及其右子树后，将双亲结点*parent中介于*x和*y之间的关键字K，作为中间关键字，
        与并x和*y中的关键字一起"合并"为一个新的结点取代*x和*y。因为*x和*y原各有Min个关键字，
        从双亲中移人的K'抵消了从*x中删除的K，故新结点中恰有2Min(即2「m/2」-2≤m-1)个关键字，
        没有破坏B-树的性质(3)。但由于K'从双亲中移到新结点后，相当于从*parent中删去了K'，若parent->keynum原大于Min，
        则删除操作到此结束；否则，同样要通过移动*parent的左右兄弟中的关键字或将*parent与其 左右兄弟合并的方法来维护B-树性质。
        最坏情况下，合并操作会向上传播至根，当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并成一个新的根，
        从而使整棵树的高度减少一层。
 */

/**
 *
 * @param t
 * @return
 */
//查找中序的前驱节点：向左然后一路向右，就能找到前驱节点
Result FindPreviousKey(BTree t,int pos){
    BTree p;
    Result r;
    p=t;
    p=p->child[pos-1];
    while(p->child[p->keynum]){
        p=p->child[p->keynum];
    }
    r.pos=p->keynum;
    r.node=p;
    r.flag=TRUE;
    return r;
}
//查找中序的后继节点：向右然后一路向左，就能找到前驱节点
Result FindNextKey(BTree t,int pos){
    BTree p;
    Result r;
    p=t;
    p=p->child[pos];
    while(p->child[0]){
        p=p->child[0];
    }
    r.pos=1;
    r.node=p;
    r.flag=TRUE;
    return r;
}
Status OrderByKey_(Result r) {
    int i, j,size;
    KeyType temp;
    BTree p=r.node,t;
    size=p->keynum;
    for (j = 0; j < size - 1; j++)            // 每次最大元素就像气泡一样"浮"到数组的最后
    {
        for (i = 0; i < size - 1 - j; i++)    // 依次比较相邻的两个元素,使较大的那个向后移
        {
            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
            if (p->data[i+1] > p->data[i+2]) {
                /** exchange data**/
                temp = p->data[i+1];
                p->data[i+1] = p->data[i + 2];
                p->data[i + 2] = temp;
                /** exchange pointer**/
                t=p->child[i];
                p->child[i]=p->child[i+1];
                p->child[i+1]=t;
            }
        }
    }
}
//向左移一位
Status btree_left_move_one(BTree *node,int data_index,int child_index){
    if(!(*node))return 0;
    if(data_index<=0)data_index=1;
    if(child_index<=0)child_index=0;
    int i;
    for(i=data_index;i<(*node)->keynum;i++){
        (*node)->data[i]=(*node)->data[i+1];
    }
    for(i=child_index;i<(*node)->keynum;i++){
        (*node)->child[i]=(*node)->child[i+1];
    }
}
//向左移一位
Status btree_left_move(Result r){
    BTree p=r.node;
    int i;
    if(r.pos<=0)i=p->keynum;
    for(i=r.pos;i<p->keynum;i++){
        p->data[i]=p->data[i+1];
    }
    if(r.null_child_index<=0)i=p->keynum;
    for(i=r.null_child_index;i<p->keynum;i++){
        p->child[i]=p->child[i+1];
    }
}
Status btree_right_move(Result r){
    BTree p=r.node,t;
    int i;
    for(i=r.pos;i>1;i--){
        p->data[i]=p->data[i-1];
    }
    for(i=r.null_child_index;i>0;i--){
        p->child[i]=p->child[i-1];
    }
}
Status DeleteKey(Result res,BTree *b){
    BTree pnod=NULL,parent=NULL,leftChild=NULL, rightChild=NULL,ptmp=NULL;
    int min,max,index,i,j;
    min=MinKeyNum;
    max=MaxKeyNum;
    pnod=res.node;
    if(!pnod)return ERROR;
    /**
         * 情形一：若x->keynum>Min，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。
         * 删除后重新调整位置
         * */
    if(pnod->keynum > min){
        btree_left_move(res);
        pnod->data[pnod->keynum]=KeyType_NULL;
        pnod->child[pnod->keynum]=NULL;
        pnod->keynum--;
    }else{
        /**
         * 情形二:
         * 若x->keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。
         * 若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，
         * 而将*parent中相应的关键字下移至x中
         * */
        Boolean bl=FALSE,br=FALSE;
        parent=pnod->parent;
        index=Search(parent,pnod->data[pnod->keynum]);
        //优先向左,then forward right
        if(index>=1){
            leftChild=parent->child[index-1];
            if(leftChild->keynum>min)bl=TRUE;
        }
        if(index<parent->keynum){
            rightChild=parent->child[index+1];
            if(rightChild->keynum>min)br=TRUE;
        }
        if(bl&&leftChild){
            btree_right_move(res);
            pnod->data[1]=parent->data[index];
            pnod->child[0]=leftChild->child[leftChild->keynum];
            parent->data[index]=leftChild->data[leftChild->keynum];
            leftChild->data[leftChild->keynum]=KeyType_NULL;
            leftChild->child[leftChild->keynum]=NULL;
            leftChild->keynum--;
            //OrderByKey_(res);
            //如果删除f，等下验证,插入之后要进行排序
        }else if(br&&rightChild){
            btree_left_move(res);
            pnod->data[pnod->keynum]=parent->data[index+1];
            pnod->child[pnod->keynum]=rightChild->child[0];
            parent->data[index+1]=rightChild->data[1];
            btree_left_move_one(&rightChild,1,0);
            rightChild->data[rightChild->keynum]=KeyType_NULL;
            rightChild->child[rightChild->keynum]=NULL;
            rightChild->keynum--;
            //OrderByKey_(res);
        }else{
            /**情形三:**/
            //合并左结点优先，如左结点不符合条件合并右结点
            if((!bl)&&leftChild){
                leftChild->data[leftChild->keynum+1]=parent->data[index];
                leftChild->keynum++;
                //当前节点的元素逐个移到左节点，除被删除元素外
                j=leftChild->keynum;
                for(i=1;i<=pnod->keynum;i++){
                    if(res.pos==i)continue;//丢弃删除的元素，不迁移
                    leftChild->data[++leftChild->keynum]=pnod->data[i];
                }
                //迁移孩子
                for(i=0;i<=pnod->keynum;i++){
                    //丢弃的孩子不迁移
                    if(pnod->child[i]) {
                        pnod->child[i]->parent=leftChild;
                        leftChild->child[j++] = pnod->child[i];
                    }
                }
                res.pos=index;
            } else if((!br)&&rightChild){
                //腾出空位:腾出右节点的KEY,child,让父节点的KEY,child 和插入
                j=pnod->keynum+rightChild->keynum;
                for(i=0;i<rightChild->keynum;i++){
                    rightChild->data[j-i]=rightChild->data[rightChild->keynum-i];
                    rightChild->child[j-i]=rightChild->child[rightChild->keynum-i];
                }
                rightChild->child[j-i]=rightChild->child[rightChild->keynum-i];
                rightChild->data[pnod->keynum]=parent->data[index+1];
                //rightChild->child[pnod->keynum]=pnod->child[res.pos-1];
                rightChild->keynum++;
                //迁移元素
                for(i=1,j=1;j<=pnod->keynum;i++,j++){
                    //丢弃删除的元素，不迁移
                    if(res.pos!=j){
                        rightChild->data[i]=pnod->data[j];
                        rightChild->keynum++;
                    }else{
                        i--;
                    }
                }
                //迁移孩子
                for(i=0,j=0;j<=pnod->keynum;i++,j++){
                    //丢弃的孩子不迁移
                    if(pnod->child[j]){
                        pnod->child[j]->parent=rightChild;
                        rightChild->child[i]=pnod->child[j];
                    }else{
                        i--;
                    }
                }
                res.pos=index+1;
            }
            //置空,释放节点
            printf("%c\n",pnod->data[1]);
            parent->child[index]=NULL;
            pfree(pnod);
            if((!parent->parent)&&parent->keynum-1<=0){
                ptmp=parent;
                if((!bl)&&leftChild){
                    leftChild->parent=NULL;
                    parent=leftChild;
                }
                if((!br)&&rightChild){
                    rightChild->parent=NULL;
                    parent=rightChild;
                }
                printf("%c\n",ptmp->data[1]);
                pfree(ptmp);
                *b=parent;
                return 1;
            }
            res.null_child_index=index;
            res.node=parent;
            res.flag=1;
            DeleteKey(res,b);
        }


    }
    return 1;
}
/**
 *
 * @param b the tree
 * @param k the key
 * @return
 */
Status DeleteBTree(BTree *b, KeyType k){
    Result res,r2;
    BTree p,pnod=NULL,parent=NULL,leftChild=NULL, rightChild=NULL;
    int min,max,index,i,j;
    min=MinKeyNum;
    max=MaxKeyNum;
    p=*b;
    if(!p)return ERROR;
    KeyType keytmp,keytpm2;
    res.null_child_index=-1;
    res.pos=-1;
    res.flag=-1;
    res.node=NULL;
    res=BTreeSearch(p,k);
    if(!res.flag)return FALSE;
    pnod=res.node;
    //非叶子节点
    //step1;
    if(pnod->child[0]){
        r2=FindNextKey(pnod,res.pos);
        keytmp=r2.node->data[r2.pos];
        DeleteBTree(&r2.node, keytmp);
        pnod->data[res.pos]=keytmp;
    //step2:
    }else{
        DeleteKey(res,b);
    }
}

/*-----------------------------------------Insert--------------------------------------------*/
//插入一个key，n+1是真正插入的位置
void InsertKey(BTree *t, KeyType k, int n) {
    BTree p;
    int i;
    p = *t;
    for (i = m - 1; i > n; i--) {
        p->data[i + 1] = p->data[i];
    }
    p->data[n + 1] = k;
    p->keynum++;
}
//插入一个key，实现上调用了InsertKey()
void Insert(BTree *t, KeyType k) {
    int position;
    position = Search(*t, k);
    InsertKey(t, k, position);
}
//创建一个新的节点，初始化新节点
void NewNode(BTree *node, KeyType k) {
    int i;
    (*node) = palloc(sizeof(BTNode));
    (*node)->keynum = 1;
    (*node)->data[1] = k;
    (*node)->parent = NULL;
    for (i = 0; i < m + 1; i++)
        (*node)->child[i] = NULL;
}
//节点分裂，如果符合再分裂的条件递归之
void Split(BTree *t) {
    BTree parent, node, p;
    int i,j, s = MiddleKey;
    p = *t;
    // if a new root
    if (!p->parent) {
        NewNode(&parent, p->data[s]);
        NewNode(&node, p->data[s + 1]);
        p->parent = parent;
        node->parent = parent;
        parent->child[0] = p;
        parent->child[1] = node;
    } else {
        parent = p->parent;
        Insert(&parent, p->data[s]);
        //
        NewNode(&node, p->data[s + 1]);
        node->parent = parent;
        i=Search(parent,p->data[p->keynum]);
        for (j=parent->keynum; j>i; j--) {
            parent->child[j]=parent->child[j-1];
        }
        parent->child[i] = node;

    }
    //把m+1/2右边的key搬到右边的新节点中，同时左边该key置空，numkey为s-1
    for (i = s + 2;i <= p->keynum; i++) {
        //move key to new node,then set null
        Insert(&node, p->data[i]);
        p->data[i]=KeyType_NULL;

    }
    //move pointer to new node,then set null
    if(p->child[0]){
        for(i=s,j=0;i<=p->keynum;j++,i++){
            //Belong to new daddy
            p->child[i]->parent=node;
            node->child[j]=p->child[i];
            p->child[i]=NULL;
        }
    }
    p->data[s]=KeyType_NULL;
    p->data[s+1]=KeyType_NULL;
    p->keynum=s-1;
    //如果父节点满了，递归之
    if (parent->keynum >= m)
        Split(&parent);
}
Status InsertBTree(BTree *t, KeyType k) {
    int i = 0, s = 0;
    BTree p;
    Result r;
    // if tree is null,insert first key
    if (!(*t)) {
        NewNode(t, k);
        return OK;
    } else {
        r = BTreeSearch(*t, k);
        if (r.flag == 1)return Repetition;
        else if (r.flag == 0) {
            InsertKey(&r.node, k, r.pos);
            if (r.node->keynum >= m) {
                Split(&r.node);
                //如有下次插入，须从根节点开始
                p = r.node;
                while(p->parent)
                    p=p->parent;
                *t=p;
            }
        }
        return  OK;
    }

}
/*-----------------------------------------Print Btree--------------------------------------------*/
// 按层次打印 B 树
/**
 *  layer init is 1
 */
void BTree_print(BTree tree, int layer)
{
    int i;
    BTNode *node = tree;

    if (node) {
        //display layer by space key
        for(i=1;i<layer;i++){
            printf("%c",' ');
            printf("%c",' ');
            printf("%c",' ');
        }

        printf("第 %d 层， %d node : ", layer, node->keynum);

        //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。
        for (i = 1; i <=node->keynum; ++i) {
            //for (i = 0; i < node->keynum; ++i) {
            printf("%c ", node->data[i]);
        }
        printf("\n");
        ++layer;
        for (i = 0 ; i <= node->keynum; i++) {
            if (node->child[i]) {
                BTree_print(node->child[i], layer);
            }
        }
    }
    else {
        printf("树为空。\n");
    }
}
int BTree_Main() {
    int num=21;
    //char r[21] = {'C','N','G','A','H','E', 'K','Q','M','F','W','L','T','Z','D','P','R','X','Y','S','B'};
    char r[21] = {'C','N','G','A','H','E', 'K','Q','M','F','W','L','T','Z','D','P','R','X','Y','S','V'};
    //char r[22] = {'C','N','G','A','H','E', 'K','Q','M','F','W','L','T','Z','D','P','R','X','Y','S','I','J'};
    //char r[23] = {'C','N','G','A','H','E', 'K','Q','M','F','W','L','T','Z','D','P','R','X','Y','S','B','I','J'};
    //char r[20] = {'a','g','f','b','k','d','h','m','j','e','s','i','r','x','c','l','n','t','u','p'};
    //char r[21] = {'a','g','f','b','k','d','h','m','j','e','s','i','r','x','c','l','n','t','u','p','y'};
    BTree T = NULL;
    Status s;
    int i;
    for (i = 0; i < num; i++) {
        s=InsertBTree(&T, r[i]);
    }
    BTree_print(T,1);
    /**---------------------------------**/
    printf("delete : %c\n",'Y');
    DeleteBTree(&T,'Y');//向左取Key
    BTree_print(T,1);
    /**---------------------------------**/
    printf("delete : %c\n",'Y');
    DeleteBTree(&T,'Y');
    BTree_print(T,1);
    /**---------------------------------**/
    printf("delete : %c\n",'Z');
    DeleteBTree(&T,'Z');//向右取Key
    BTree_print(T,1);
    /**---------------------------------**/
    printf("delete : %c\n",'k');
    DeleteBTree(&T,'k');
    BTree_print(T,1);
    printf("finish \n");
    return 0;
}
